package basic.courseLearn02.sort;

import basic.courseLearn01.utils.FunctionSort;
import basic.courseLearn01.utils.SortUtils;
import org.junit.Test;
import basic.utils.CommonUtil;

public class QuickSort implements FunctionSort {


    @Override
    public int[] sort(int[] result) {

        quickSort(result,0,result.length-1);

        return result;
    }

    @Test
    public void test(){
        SortUtils.executeCheckAlgorithm(1_0000,10000,10000,this);
    }

    public void quickSort(int[] arr,int letfIndex,int rightIndex){
        if (letfIndex==rightIndex){ //递归截止条件
            return ;
        }
        int standardIndex = (int)Math.random()*(rightIndex-letfIndex+1)+letfIndex;  //随机选择标准
        int[] location=new int[2];
        location = netherlandsFlag(arr,letfIndex,rightIndex,arr[standardIndex]);    //三色国旗操作，返回flag的位置
        quickSort(arr,letfIndex,location[0]);
        quickSort(arr,location[1],rightIndex);
    }

    //荷兰三色国旗，返回flag最初出现的位置前一个，和最后出现的位置后一个
    public int[] netherlandsFlag(int[] arr,int left,int right,int flag){
        int leftIndex=left,rightIndex=right;
        for (int i = leftIndex; i <=rightIndex; i++) {
            if (arr[i]<flag){       //小数
                if (i>leftIndex){
                    CommonUtil.swap(arr,leftIndex,i);
                }
                leftIndex++;
            }else if(arr[i]>flag) {   //大数
                CommonUtil.swap(arr,i,rightIndex);
                rightIndex--;
                i--;
            }
        }
        //记录flag位置
        int[] location=new int[]{left,right};
        for (int i=left;i<=right;i++){
            if (arr[i]<flag){
                location[0]=i;
            }else if (arr[i]>flag){
                location[1]=i;break;
            }
        }
        return location;
    }
}
